package array.滑动窗口;

import org.junit.Test;

/**
 * 给定一个含有 n 个正整数的数组和一个正整数 target 。
 *
 * 找出该数组中满足其和 ≥ target 的长度最小的 连续子数组 [numsl, numsl+1, ..., numsr-1, numsr] ，并返回其长度。如果不存在符合条件的子数组，返回 0 。
 *
 */
public class 长度最小的子数组 {
    //先理解暴力破解版
    @Test
    public int minSubArrayLen1(int target, int[] nums) {
        int subLength=0,sum=0,res=Integer.MAX_VALUE;
        for(int i=0;i<nums.length;i++){
            sum=0;//每次新的循环都应该清零
            for (int j=i;j<nums.length;j++){
                //找最小的子串
                sum+=nums[j];
                //找到
                if(sum>=target){
                    subLength=j-i+1;
                    res=subLength<res?subLength:res;
                    break;//此时便是本数开头最小
                }
            }
        }
        return res==Integer.MAX_VALUE?0:res;
    }
    //O(n^2)

    @Test
    // 滑动窗口(双指针)
    public int minSubArrayLen2(int s, int[] nums) {
        int left = 0;
        int sum = 0;
        int result = Integer.MAX_VALUE;
        for (int right = 0; right < nums.length; right++) {
            sum += nums[right];
            while (sum >= s) {
                result = Math.min(result, right - left + 1);
                sum -= nums[left++];
            }
        }
        return result == Integer.MAX_VALUE ? 0 : result;
    }
}
